1、lru
思想：就是unordered_map加一个双向链表，map用来查找当前链表是否由节点，双向链表用来读取和删除节点；
struct listnode
{
    int key;
    int val;
    listnode* next;
    listnode* prev;
    listnode(int k,int v)
        :key(k),val(v),prev(nullptr),next(nullptr)
        {}
};
class Solution {
private:
    int size=0;
    listnode* head;
    listnode* tail;
    unordered_map<int, listnode*> mp;
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    void insertfirst(listnode* node) 
    {
        node->prev=this->head;
        node->next=this->head->next;
        this->head->next->prev=node;
        
        this->head->next=node;
    }
    void movetohead(listnode* node)
    {
        if(node->prev==this->head)
            return ;
        //先将该节点移除下来，然后插入到头部
        node->prev->next=node->next;
        node->next->prev=node->prev;
        insertfirst(node);
    }
    void removelast()
    {
        //删除节点，肯定得删除mp中的记录
        mp.erase(this->tail->prev->key);
        this->tail->prev->prev->next=this->tail;
        this->tail->prev=this->tail->prev->prev;
    }
    void set(int key,int val)
    {
        if(mp.find(key)==mp.end())
        {
            listnode* node=new listnode(key,val);
            mp[key]=node;
            if(this->size<=0)
                removelast();
            else
                this->size--;
            insertfirst(node);
        }
        else
        {
            mp[key]->val=val;
            movetohead(mp[key]);
        }
    }
    int get(int key)
    {
        int ret=-1;
        if(mp.find(key)!=mp.end())
        {
            ret=mp[key]->val;
            movetohead(mp[key]);
        }
        return ret;
    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> v;
        if(operators.empty()||k<1)
            return v;
        this->head=new listnode(0,0);
        this->tail=new listnode(0,0);
        this->head->next=this->tail;
        this->tail->prev=this->head;
        this->size=k;
        for(auto op:operators)
        {
            if(op[0]==1)
                set(op[1],op[2]);
            else if(op[0]==2)
            {
                int x=get(op[1]);
                v.push_back(x);
            }
        }
        return v;
    }
};